CURSUL nr.02
predat in ziua de 11 octombrie 2010
in lucru acum....
Volumul de prelucrari VP() porneste de la ipoteza simplificatoare ca toate instructiunile sunt de aceeasi complexitate.
Pentru structura liniara SL, volumul de prelucrari VP(SL) = n, daca n este numarul de instructiuni care formeaza secventa.
Pentru secventa:
a=5;
b=a;
c=a+b;
d=1./a;
e=c*d;
volumul de prelucrari este:
VP(SL)=5.
Pentru structura alternativa SA, volumul de prelucrari tine seama de:
- probabilitatea p cu care se executa ramura DA a structurii
- de probabilitatea q cu care se executa ramura NU a structurii
- VP(S1) volumul de prelucrari al secventei de pe ramura DA
- VP(S2) volumul de prelucrari al secventei de pe ramura NU
ceea ce conduce la formula:VP(S1) volumul de prelucrari al secventei de pe ramura DA
VP(SA)=1 + p * VP(S1) + q * VP(S2)
Pentru structura repetitiva SR() volumul de prelucrari tine seama de:
- numarul n de repetari
- VP(S1) ce corespunde secventei de repetat.
Inseamna ca volumul de prelucrari este:
VP(SR)= 1 + n * (1 + VP(S1)).
Pentru secventa SPM, de program destinata produsului a doua matrice a[m][n] si b[m][p]:
for(i=0; i
for(j=0; j
{
cij=0;
for(k=0; k
cij+=a[i][k]*b[k][j];
c[i][j]=cij;
}
volumul de prelucrari include:
VP(SPM)= m (pentru for (i=0...))+ m*p (pentru for(j=0;....)) + m*p (pentru cij=0) +n*p*m (pentru for(k=0;...)) + n*p*m (pentru cij+=...) + m*p(pentru c[i][j]=cij.
Adica
VP(SPM)= m + 3*m*p + 3*m*p*n
Complexitatea programelor se obtine fie folosind graful asociat programului, fie folosind structura programului, cu operanzi si operatori.
Structura programului presupune numararea operanzilor si a operatorilor.
Se foloseste relatia:
C = n 1 LOG 2 (n 1) + n 2 LOG 2 (n 2),
unde:
n 1 - numar de operatori
n 2 - numar de operanzi.
Pentru secventa:
a=1+1+1+1+1;
b+=a/d++ +c--;
b++ = a -- + b++/c--;
operatorii, operanzii folositi si frecventele lor sunt:
= 2
+= 1
++ 3
-- 3
+ 6
/ 2
1 5
a 3
b 3
c 2
d 1
rezulta:
n 1 = 17
n 2 = 14
colplexitatea fiind:
C = 17*LOG 2(17) + 14 *LOG 2(14).
Complexitatea folosind graful asociat programului porneste de la:
NN - numarul de noduri din graf
NA - numarul de arce din graf
C = NA - NN +2
In cazul structurii liniare cu n noduri si n-1 arce, complexitatea este C=1.
Pentru o structura arborescenta binara echilibrata cu n niveluri, numerotate cu 0, 1, ..., n-1 vor exista 2n noduri si 2n - 2 arce, iar complexitatea este data de relatia:
C = (2n -2)- (2n - 1)+ 2 = 1
In cazul unei secvente de forma:
if(a== 2) if(c==3) e=7;
else e=-1;
else if (d==3) e-12; else e=-2;
NN=10 si NA= 12 c eea ce conduce la complexitatea c=12-10+2=4.
Crearea unui element dintr-o structura de date presupune:
- stabilirea structurii informatiei utile
- scrierea programului care preia datele cu care se initializeaza o variabila definita pentru informatia utila
- apelarea unei proceduri pentru crearea unui element
- folosirea elementului creat pentru a-l lega la restul elementelor din structura.
Procedura pentru crearea elementului contine:
- tipul rezultatului returnat care este pointer spre tipul asociat structurii ce se creaza
- numele procedurii de creare element
- lista de parametri ce contine tipul informatiei utile si o variabila cu rol de parametru formal
- o instructiune pentru alocare memorie
- o instructiune care verifica daca alocarea s-a efectuat cu succes
- alocarea fara succes este insotita rde returnare NULL
- alocarea cu succes va determina initializarea prin copiere sau atribuire a campurilor din informatia utila a elementului de structura dinamica
initializarea campurilor de legatura cu NULL
- returnarea rezultatului procesului de cderare, adica a unui pointer.
Pentru cerarea cu initializare a unui element de lista simpla, procedura este:
..............
Pentru cerarea cu initializare a unui element de lista dubla, procedura este:
..............
Pentru cerarea cu initializare a unui element de arbore binar, procedura este:
..............
Trebuie ca procedura sa conduca la cat mai putine modificari la celelalte proceduri din biblioteca.
Agregarea de proceduri corespunde situatiei in care exista mai multe proceduri care abordeaza partial problematica. Se scriu proceduri pentru:
- concatenarea masivului x[N] cu masivul y[M]
- concatenarea masivului y[N] cu masivul x[M]
- se cere scrierea unei proceduri care concateneaza x[N] cu y[M] sau y[M] cu x[N]
- adunarea matricei a[m][n] cu matricea b[m][n]
- adunarea matricei at[m ][n] cu matricea b[m][n]
- adunarea matricei a[m][n] cu matricea bt[m][n]
- adunarea matricei at[m][n] cu matricea bt[m][n]
- adunarea matricelor a[][] si b[][] in oricare dintre combinatii intr-o singura procedura.
Daca sunt scrise proceduri pentru:
- alegere element minim din sirul x[N]
- alegere element maxim din sirul x[N]
- sortare crescatoare a sirului x[N]
- sortare descrescatoare a sirului x[N]
- adunarea elementelor sirului x[N]
se pune problema scrierii unei proceduri unice care sa efecteze una dintre aceste prelucrari.
Este o problema de agregare proceduri.
Pentru adunarea de matrice procedura agregata este:
....................
Pentru calculele pe sir, procedura este:
....................
Pentru concatenare, procedura este:
....................
Se observa aparitia unei variabile de control, iar prin testarea ei se obtine trecerea la secventa care efectueaza prelucrarea ceruta.
Elaborarea referatului va impune:
- structurarea in cel mult 6 parti
- construirea unei bibliografii corecte in care se vor regasi toate elementele de identificare a unei carti, a unui articol sau a unei comunicari.
referatul trebuie sa aiba maximum 5 pagini.
1/2 pagina introducere si 1/2 pagina concluzii.
Structura va incllude:
1. Introducere unde se stabileste obiectiv, se precizeaza necesitatea, mijloacele
2. Prezentarea problemei
3. Prezentarea solutiei: structurile folosite, motivatia alegerii unei structuri.
4. Descrierea programului: biblioteci utilizate, proceduri, parametri, restrictii, volum prelucrari, complexitate
5. Rezultatele testarii: seturi de date, mesaje, cum au fost corectate erorile.
6. Concluzii
Bibliografie
Referatul NU va contine sub nicio forma verbul A PUTEA si negatia NU!!!!
Cercul de structuri de date se adreseaza celor care:
- doresc sa urmeze un PhD
- doresc sa lucreze in cercetare
- vor sa plece la studii in straionatate in zona informaticii.
La cerc vor invata:
- sa construiasca o bibliografie
- sa faca o sinteza documentara
- sa dezvolte o analiza comparata
- sa ierarhizeze solutii
- sa caute elemente de solutii originale si sa le prezinte avantajele.
Eventual, daca sunt perseverenti, acestia vor si lucra intr-o echipa cu bune sanse de a publica un articol.
Structura bibliotecii de proceduri
Analiza comparata intre lucru cu structuri dinamice si lucru cu structuri statice
Salvarea informatiei volatile presupune:
- crearea cu initializare a structurii dinamice
- salvarea intr-un fisier a informatiei utile din structura dinamica
preluarea din fisier in structura dinamica a datelor la o noua lansare a aplicatiei, cu salvare inainte de incheiere lucrului.
Va trebui sa se gaseasca un mod de a asigura lucru corect, fara a salva si valorile variabilelor pointer de legatura.
Reorganizarea de date
afisat azi 11octombrie 2010
REVENIRE